// scaup - Scala up!
// (c) 2008-2010, Normen Müller, normen.mueller@gmail.com  
// $Id: Differ.scala 50 2010-01-14 22:23:33Z normen.mueller $
package scaup.util

import java.io.File

import scaup.Views._

/** ASCII differencing options
 * 
 * @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 * @version 0.0.3 */
object ASCIIDiffOption extends Enumeration {
  val NORMAL, UNIFIED = Value
}
import ASCIIDiffOption._

/** Differencing algorithms
 * 
 * @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 * @version 0.0.3 */
object Differ {  
  def asciidiff(src: File,tgt: File): String = asciidiff(NORMAL, src, tgt)
  
  def asciidiff(O: ASCIIDiffOption.Value,src: File,tgt: File): String = O match {
    case NORMAL =>
      asciidiff(O, src.content, tgt.content)
      
    case UNIFIED =>
      val formatter = new java.text.SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSSSSSSSS Z")
      val buf = new StringBuilder
      buf append "--- " append src.ap append " " append formatter.format(new java.util.Date())
      buf append "\n"
      buf append "+++ " append tgt.ap append " " append formatter.format(new java.util.Date())
      buf append "\n"
      buf append asciidiff(O, src.content, tgt.content)
      buf.toString
  }
  
  def asciidiff(src: String,tgt: String): String = asciidiff(NORMAL,src,tgt)
  
  def asciidiff(O: ASCIIDiffOption.Value, src: String, tgt: String): String =
    new Differ[String](src.linesWithSeparators.toList,tgt.linesWithSeparators.toList).diff(O)
}

/** Primitive, ie. without any optimization, implementation of GNU diff.
 * 
 *  <p>cf. <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem">LCS</a></p>
 * 
 * @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 * @version 0.0.3 */
private [util] class Differ[T <% Ordered[T]](X: List[T],Y: List[T]) {
  import scala.collection.immutable.{SortedMap,TreeMap}
  
  def diff(O: ASCIIDiffOption.Value): String = O match {
    case NORMAL  => normal(ed(bt(lcs(),X,Y,X.length,Y.length,TreeMap.empty[Int,Int])))
    case UNIFIED => unified(ed(bt(lcs(),X,Y,X.length,Y.length,TreeMap.empty[Int,Int])))
  }

  /* build lcs table */
  private def lcs(): Array[Array[Int]] = {
    val C = new Array[Array[Int]](X.length+1,Y.length+1)
    for(i <- 1 to X.length)
      for(j <- 1 to Y.length)        
        if(X(i-1) == Y(j-1))
          C(i)(j) = C(i-1)(j-1)+1
        else C(i)(j) = C(i)(j-1) max C(i-1)(j)
    C
  }
  
  /* back-trace all */
  private def bt(C: Array[Array[Int]],X: List[T],Y: List[T],i: Int,j: Int,m: SortedMap[Int,Int]): SortedMap[Int,Int] = {
    if(i == -1 || j == -1)
      m
    else if((X isDefinedAt i) && (Y isDefinedAt j) && X(i) == Y(j))
      if(m.keySet.exists(k => m(k) == j && k < i))
        m
      else bt(C,X,Y,i-1,j-1,((n: SortedMap[Int,Int]) => n -- (n.keySet filter (k => n(k) == j && k > i)))(m+{(i,j)}))
    else {
      var n: SortedMap[Int,Int] = m
      if(i > 0 && j > 0 && C(i)(j-1) >= C(i-1)(j))
        n = bt(C,X,Y,i,j-1,n)
      if(i > 0 && j > 0 && C(i-1)(j) >= C(i)(j-1))
        n = bt(C,X,Y,i-1,j,n)
      n
    }
  }
  
  /* build edit script */
  import scala.collection.mutable.ListBuffer
  private def ed(m: SortedMap[Int,Int]): List[Delta] = {
    var xi = 0
    var yi = 0
    var pending: Option[Delta] = None  
    val ds = new ListBuffer[Delta]()
    while(xi <= {if(m.size == 0) 0 else 1+m.lastKey} - 1) {
      if(m contains xi) {
        while (yi < m(xi)) {
          pending = onBNotA(pending,xi,yi)
          yi += 1
        }
        pending = onMatch(ds,pending,xi,yi)
        yi += 1
      } else pending = onANotB(pending,xi,yi)
      xi += 1
    }
    while(xi < X.length || yi < Y.length) {
      if (xi == X.length && yi < Y.length) while (yi < Y.length) { pending = onBNotA(pending,xi,yi); yi += 1 }
      if (yi == Y.length && xi < X.length) while (xi < X.length) { pending = onANotB(pending,xi,yi); xi += 1 }
      if (xi < X.length) { pending = onANotB(pending,xi,yi); xi += 1 }
      if (yi < Y.length) { pending = onBNotA(pending,xi,yi); yi += 1 }
    }    
    pending match {
      case Some(p) => ds += p; ds.toList
      case None => ds.toList
    }    
  }
  
  private def onANotB(pending: Option[Delta],x: Int,y: Int): Option[Delta] = pending match {
    case Some(Delta(ds,de,as,ae)) => Some(Delta(x min ds,x max de,as,ae))
    case None                     => Some(Delta(x,x,y,-1))
  }
  
  private def onBNotA(pending: Option[Delta],x: Int,y: Int): Option[Delta] = pending match {
    case Some(Delta(ds,de,as,ae)) => Some(Delta(ds,de, y min as, y max ae)) 
    case None                     => Some(Delta(x, -1, y, y))
  }
  
  private def onMatch(ds: ListBuffer[Delta],pending: Option[Delta],x: Int,y: Int): Option[Delta] = pending match {
    case Some(p) => ds += p; None
    case None    => pending
  }
  
  /* slurp edit script into string representation (GNU diff normal output format) */
  private def normal(ds: List[Delta]): String = (new StringBuilder /: ds)((b,d) => {
    b append {if(d.delEnd == -1) d.delStart else 1+d.delStart} append {
      if(d.delEnd != -1 && d.delStart != d.delEnd)
        ","+(1+d.delEnd)
      else ""
    }
    b append {if(d.delEnd != -1 && d.addEnd != -1) "c" else if (d.delEnd == -1) "a" else "d"}
    b append {if(d.addEnd == -1) d.addStart else 1+d.addStart} append {
      if(d.addEnd != -1 && d.addStart != d.addEnd)
        ","+(1+d.addEnd)
      else ""
    }
    b append "\n"
    b append {
      if (d.delEnd != -1)
        X.slice(d.delStart,d.delEnd+1).mkString("< ", "< ", "") + {if(d.addEnd != -1) "---\n" else ""}
      else ""}
    b append {if (d.addEnd != -1) Y.slice(d.addStart,d.addEnd+1).mkString("> ", "> ", "") else ""}
  }).toString
  
  /* slurp edit script into string representation (GNU diff unified output format) */
  private def unified(ds: List[Delta]): String = (new StringBuilder(
    "@@ -" + {
      if(ds.head.delEnd == 0)
        ds.head.delEnd.abs+1
      else ds.head.delEnd.abs
    } + "," +
    (ds.last.delEnd+1) + " +" + {
      if(ds.head.addStart == 0)
        ds.head.addStart.abs+1
      else ds.head.addStart.abs}+","+(ds.last.addEnd+1)+" @@\n") /: ds)((b,d) => {
        b append (X.slice(d.delStart,d.delEnd+1) match {
          case Nil => ""
          case l@_ => l.mkString("-", "-", "") + {
            if(d.addEnd == -1)
              X.slice(d.addStart,d.addStart+1).mkString(" ", " ", "")
            else ""
          }
        })
        b append (Y.slice(d.addStart,d.addEnd+1) match {
          case Nil => ""
          case l@_ => l.mkString("+", "+", "") + {
            if(d.delEnd == -1)
              X.slice(d.addStart,d.addEnd).mkString(" ", " ", "")
            else ""
          }
        })
      }).toString  
}

private [util] case class Delta(var delStart: Int,var delEnd: Int,var addStart: Int,var addEnd: Int)

//  def lcs(): String = backTrace(tbl(),X,Y,X.length,Y.length)
//  def lcss(): Set[String] = backTraceAll(tbl(),X,Y,X.length,Y.length)
//  private def backTrace(C: Array[Array[Int]],X: Array[T],Y: Array[T],i: Int,j: Int): String = 
//    if(i == 0 || j == 0)
//      ""
//    else if(X(i-1) == Y(j-1))
//      backTrace(C,X,Y,i-1,j-1) + X(i-1)
//    else if(C(i)(j-1) > C(i-1)(j))
//      backTrace(C,X,Y,i,j-1)
//    else backTrace(C,X,Y,i-1,j)  
//  private def backTraceAll(C: Array[Array[Int]],X: Array[T],Y: Array[T],i: Int,j: Int): Set[String] =
//    if(i == 0 || j == 0)
//      Set.empty[String]
//    else if(X(i) == Y(j))
//      (Set.empty[String] /: backTraceAll(C,X,Y,i-1,j-1))((s,z) => s + (z + X(i))) 
//    else {
//      var R = Set.empty[String]
//      if(C(i)(j-1) >= C(i-1)(j))
//        R = backTraceAll(C, X, Y, i, j-1)
//      if(C(i-1)(j) >= C(i)(j-1))
//         R = R ++ backTraceAll(C,X,Y,i-1,j)
//      R
//    }
